home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / sbprolog / amiga / v3_1 / sbp3_1e.lzh / TREESORT.PL < prev    next >
Text File  |  1991-10-31  |  2KB  |  62 lines
  1. /* From the book PROLOG PROGRAMMING IN DEPTH
  2.    by Michael A. Covington, Donald Nute, and Andre Vellino.
  3.    Copyright 1988 Scott, Foresman & Co.
  4.    Non-commercial distribution of this file is permitted. */
  5.  
  6. /* TREESORT.PL */
  7. /* Sorting a list by converting it into
  8.    a binary tree, then back into a list */
  9.  
  10. treesort(List,NewList) :-
  11.                   list_to_tree(List,Tree),
  12.                   tree_to_list(Tree,NewList).
  13.  
  14. /*
  15.  * insert(Element,Tree,NewTree)
  16.  *   inserts Element into Tree giving NewTree.
  17.  */
  18.  
  19. insert(NewItem,empty,tree(NewItem,empty,empty)) :- !.
  20.  
  21. insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)) :-
  22.      NewItem < Element,
  23.      !,
  24.      insert(NewItem,Left,NewLeft).
  25.  
  26. insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)) :-
  27.      insert(NewItem,Right,NewRight).
  28.  
  29. /*
  30.  * insert_list(List,Tree,NewTree)
  31.  *   inserts all elements of List into Tree giving NewTree.
  32.  */
  33.  
  34. insert_list([Head|Tail],Tree,NewTree) :-
  35.      !,
  36.      insert(Head,Tree,MiddleTree),
  37.      insert_list(Tail,MiddleTree,NewTree).
  38.  
  39. insert_list([],Tree,Tree).
  40.  
  41. /*
  42.  * list_to_tree(List,Tree)
  43.  *   inserts all elements of List into an initially empty tree.
  44.  */
  45.  
  46. list_to_tree(List,Tree) :- insert_list(List,empty,Tree).
  47.  
  48. /*
  49.  * tree_to_list(Tree,List)
  50.  *   places all elements of Tree into List in sorted order.
  51.  */
  52.  
  53. tree_to_list(Tree,List) :-
  54.      tree_to_list_aux(Tree,[],List).
  55.  
  56. tree_to_list_aux(empty,List,List).
  57.  
  58. tree_to_list_aux(tree(Item,Left,Right),OldList,NewList) :-
  59.      tree_to_list_aux(Right,OldList,List1),
  60.      tree_to_list_aux(Left,[Item|List1],NewList).
  61. 
  62.